/*
https://leetcode.cn/problems/delete-and-earn/submissions/567937417/
740. 删除并获得点数
完成日期：2024/9/6
*/

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int m;
        if (!nums.empty()){
            m=*max_element(nums.begin(),nums.end());
        }
        //找到数组中的最大值
        vector<int>sum(m+1);
        vector<int>f(m+1);
        for(int x:nums)
            sum[x]+=x;
        f[0]=0;
        f[1]=sum[1];
        for(int i=2;i<=m;i++)
        {
            f[i]=max(f[i-1],f[i-2]+sum[i]);
        }
        //打家劫舍的模版
        return f[m];
    }
    
};
